/******************************************************************************
 * SteinerConstrainedPathSolve.hpp: Interface for Steiner Constrained Path Solver class.
 *
 * Author: Pedro Henrique Del Bianco Hokama <hokama@ic.unicamp.br>
 * based on: Carlos Eduardo de Andrade <andrade@ic.unicamp.br>
 *
 * (c) Copyright 2011 Institute of Computing, University of Campinas.
 *     All Rights Reserved.
 *
 *  Created on : Oct 01, 2012 by hokama
 *
 * This software is licensed under the Common Public License. Please see
 * accompanying file for terms.
 *****************************************************************************/

#ifndef STEINERCONSTRAINEDPATHSOLVER_HPP
#define STEINERCONSTRAINEDPATHSOLVER_HPP

#include <lemon/list_graph.h>
using namespace lemon;

/**
 * \brief Steiner Constrained Path Solver description.
 * \author Pedro Henrique Del Bianco Hokama <hokama@ic.unicamp.br>
 * \date 2012
 *
 * This class contains the description a generic Steiner Constrained Path Solver.
 */
class SteinerConstrainedPathSolver {
    public:
        /** \name Enumeration Definitions */
        /// Indica o status pos-execucao dos algoritmos.
        enum ResultType {
            /// Encontrou uma solucao uma solucao exata dentro do tempo limite de
            /// tempomax. Isto eh apenas para os algoritmos exatos.
            EXACT_SOLUTION = 0,

            /// Encontrou uma solucao viavel (nao necessariamente otima) dentro do
            /// tempo limite de tempomax. Isto eh apenas para os algoritmos exatos.
            EXACT_VIABLE_SOLUTION = 1,

            /// Naum encontrou solucao dentro do tempo maximo pelo algoritmo exato.
            EXACT_NO_SOLUTION = -1,

            /// Encontrou uma solucao viavel pela heuristica rapida.
            FAST_HEURISTIC_SOLUTION = 2,

            /// Nao encontrou solucao dentro do tempo maximo pela heuristica rapida.
            FAST_HEURISTIC_NO_SOLUTION = -2,

            /// Encontrou uma solucao viavel pela metaheuristica.
            METAHEURISTIC_SOLUTION = 3,

            /// Nao encontrou solucao dentro do tempo maximo pela metaheuristica.
            METAHEURISTIC_NO_SOLUTION = -3
        };

        /// Indica o status de uma possivel solucao
        enum SolutionStatus {
            /// Se eh uma solucao valida
            OK = 0,

            /// Se nao forma um caminho ou ele eh incorreto.
            INCORRECT_PATH,

            /// Se o valor fornecido nao esta de acordo com o valor do caminho.
            INCORRECT_VALUE,

            /// Se o caminho nao cobriu todos terminais.
            MISSING_TERMINALS,

            /// Se o caminho nao comeca ou acaba em S e T.
            MISSING_ENDPOINTS,

            // Se o caminho viola o atraso maximo
            INCORRECT_DELAY
        };
        //@}

    public:
        /** \name Constructors and Destructor*/
        //@{
        /// Default constructor.
        SteinerConstrainedPathSolver();

        /// Destructor.
        virtual ~SteinerConstrainedPathSolver() {}
        //@}

        /** \name Main Methods */
        //@{
        /** \brief Run the optimization using an exact algorithm or a metaheuristic.
         * \param max_time to execute in seconds.
         * \return a constant according to \ref ResultType.
         */
        virtual ResultType solve(const double max_time) = 0;

        /** \brief Run the optimization using a fast (polinomial) heuristic.
         * \param max_time to execute in seconds.
         * \return a constant according to \ref ResultType.
         */
        virtual ResultType solveFast(const double max_time) = 0;
        //@}

        /** \name Support Methods */
        //@{
        /** \brief Carrega uma instancia.
         * \param filename nome do arquivoque contem a instancia.
         */
        virtual bool loadInstance(const char* filename, double delayParam);

        /// Mostra a instancia carregada na tela no formato do Lemon
        virtual void displayInstance();

        /** \brief Check if solution is valid.
         *
         * \param solution lista de vertices ordenados no caminho.
         * \param value valor da solucao.
         * \return a solution status according to \ref SolutionStatus.
         */
        SolutionStatus checkSolution(const std::vector<ListGraph::Node> &solution,
                                     const double value) const;

        /** \brief Display the problem data. */
        void displaySolution(const std::vector<ListGraph::Node> &solution) const;

        /** \brief Look for terminals with degree one.
         * \return true if a terminal leaf was found.
         */
        virtual bool haveTerminalLeaves() const;
        //@}

    public:
        /** \name Data members */
        //@{
        /// Grafo no qual queremos encontrar o caminho.
        static ListGraph graph;

        /// Peso das arestas.
        static ListGraph::EdgeMap<double> length;

        /// Atraso das arestas.
        static ListGraph::EdgeMap<double> delay;

        /// Numero de terminais.
        static unsigned num_terminals;

        // Atraso total permitido
        static double delayLimit;

        /// Mapeamento dos vertices terminais.
        static ListGraph::NodeMap<bool> terminal;

        /// Mapeamento dos vertices extremos (fonte e sorverdouro, como o grafo eh nao orientado, nao importa a ordem).
        static ListGraph::NodeMap<bool> extremos;

        /** \brief Melhor solucao encontrada.
         *
         * Uma solucao e uma lista de vertices ordenados de tal maneira que
         * formem um caminho.
         */
        std::vector<ListGraph::Node> best_solution;

        /// Valor da melhor solucao.
        double solution_value;

        /** \brief Limitante inferior.
         *
         * Apenas para algoritmos exatos que nao encontraram
         * solucao otima, volta com o limitante inferior que delimita solucao
         * otima. Caso nao tenha sido encontrado nenhum limitante, volta com
         * valor \ref numeric_limits< double >::min().
         */
        double lb;

        /** \brief Limitante superior.
         *
         * Volta com o custo do caminho encontrado. Caso
         * nao tenha sido encontrado com nenhum circuito, volta com o valor
         * \ref numeric_limits< double >::max()
         */
        double ub;
        //@}
};

#endif  //STEINERCONSTRAINEDPATHSOLVER_HPP
